package interview;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import static com.study.util.LogUtil.info;
import static com.study.util.SwapUtil.swap;
import static java.util.Arrays.copyOf;

/**
 * 给1000万个数字，取出前N大的数字
 *
 * @author wangxiaozhe
 */
@Slf4j
@SuppressWarnings("all")
public class HeapSort {

    // 寻找topN，该方法改变data，将topN排到最前面
    private static void findTopN(int n, int[] data) {
        // 190602 first
    }

    @Test
    public void test() {
        int[] arr2 = new int[10000000];
        for (int i = 0; i < arr2.length; i++) {
            arr2[i] = i + 1;
        }

        int n2 = 3;
        info("原数组：{}", arr2);
        findTopN(n2, arr2);
        info("调整后(top {}: {})", n2, copyOf(arr2, n2));
    }
}































































/*
// 寻找topN，该方法改变data，将topN排到最前面
private static void findTopN(int n, int[] data) {

    // 先构建n个数的小顶堆
    build(n, data);

    // n往后的数进行调整
    for (int i = n; i < data.length; i++) {
        heapify(i, n, data);
    }
}

// 构建堆
private static void build(int topN, int[] data) {
    for (int i = 1; i < topN; i++) {
        int t = i;
        // 调整堆, 如果比自己的parent小, 就和parent交换
        while (t != 0 && data[parent(t)] > data[t]) {
            swap(data, t, parent(t));
            t = parent(t);
        }
    }
}

// 调整data[i]
private static void heapify(int i, int topN, int[] data) {
    if(data[i] <= data[0]) {
        return;
    }

    // 进来一个元素，只要比堆顶元素大，就先置换堆顶元素
    swap(data, i, 0);

    // 调整堆顶
    int t = 0;

    while( (left(t) < topN && data[t] > data[left(t)])
            || (right(t) < topN && data[t] > data[right(t)]) ) {

        if(right(t) < topN && data[right(t)] < data[left(t)]) {
            // 右孩子更小，置换右孩子
            swap(data, t, right(t));
            t = right(t);
        } else {
            // 否则置换左孩子
            swap(data, t, left(t));
            t = left(t);
        }
    }
}

// 父节点坐标 (从0开始)
private static int parent(int n) {
    return (n - 1) / 2;
}

// 左孩子坐标 (从0开始)
private static int left(int n) {
    return 2 * n + 1;
}

// 右孩子坐标 (从0开始)
private static int right(int n) {
    return 2 * n + 2;
}
*/
